package dp_package.all;

import java.util.HashMap;
import java.util.Map;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-05 12:38
 */
public class L518 {
    /*超时
    int count = 0;
    public int change(int amount, int[] coins) {
        if(amount==0) return 1;
        dfs(amount,coins,0);
        return count;
    }
    public void dfs(int amount, int[] coins,int index){
        if(amount<0){
            return;
        }
        if(amount==0){
            count++;
        }
        for (int i = index; i <coins.length ; i++) {
            amount-=coins[i];
            //可重复选中，还是从i开始
            dfs(amount, coins, i);
            amount+=coins[i];
        }
    }

     */
    //记忆化递归
    Map<String, Integer> map = new HashMap<>();

    public int change(int amount, int[] coins) {
        if (amount == 0) return 1;
        return dfs(amount, coins, 0);
    }

    public int dfs(int amount, int[] coins, int index) {
        //找到amount=0,直接返回1
        if (amount == 0) return 1;
        if (amount < 0 || index >= coins.length) return 0;
        //key
        String key = index + "-" + amount;
        //map中有，直接返回
        if (map.get(key) != null) return map.get(key);
        //1.当前不选
        //2.当前选，index不变，下次还可以选
//        int value = dfs(amount, coins, index + 1) +
//                dfs(amount - coins[index], coins, index);
        int value =0;
        for (int i = index; i <coins.length ; i++) {
            value+=dfs(amount-coins[i], coins, i);
        }
        map.put(key, value);
        return value;
    }


//    public int change(int amount, int[] coins) {
//        //dp[i]代表前i个硬币可以组成amount金额的个数
//        int[] dp=new int[amount+1];
//        //初始化
//        dp[0]=1;
//        //组合数问题，背包必须在内层循环
//        for (int c:coins) {
//            for (int i = c; i <=amount ; i++) {
//                dp[i]=dp[i]+dp[i-c];
//            }
//        }
//        return dp[amount];
//    }
    public static void main(String[] args) {
        L518 l518 = new L518();
        int change = l518.change(5, new int[]{1, 2, 5});
        System.out.println(change);
    }
}
